JOI 07本選 D 最悪の記者(難易度7)
まず, 辺を構成する2頂点に順序関係があることに注目する. このような場合はグラフで考えるのが典型である. 与えられる頂点$ iから頂点$ jに有向辺を張る. その後, トポロジカルソートをすることによって解くことができる. このグラフはDAGである(なぜなら順位が低いチームが高いチームに勝つことはない)から, 常にトポロジカルソートが可能である.
最後に複数存在するかどうかの判定について考える. 少し実験してみると, トポロジカルソートしたあとの隣り合う頂点についてすべてにもともと辺があれば1つしか存在せず, 1つでも辺がないものがあれば複数存在する(辺を構成する2頂点を並び変えられるので)ということがわかる.
よってこの問題は$ O(N+M)で解けた.